//
// Created by 麻再挺 on 2021/12/17.
//

#include "aoe.h"

//建立全局变量，保存边的最早开始时间
VertexType ve[MAX_VERTEX_NUM];
//建立全局变量，保存边的最晚开始时间
VertexType vl[MAX_VERTEX_NUM];

// AOE 网数据
int arr[] = {
        1, 2, 6,
        1, 3, 4,
        1, 4, 5,
        2, 5, 1,
        3, 5, 1,
        4, 6, 2,
        5, 7, 9,
        5, 8, 7,
        6, 8, 4,
        7, 9, 2,
        8, 9, 4
};

/**
 * 查找结点位置
 * @param g 网
 * @param v 索引
 * @return 索引
 */
int LocateAoeVex(AOEGraph param, int v);

/**
 * 统计图中各顶点的入度
 * @param g 图
 * @param arr
 */
void FindInDegree(AOEGraph *g, int inDegree[]);

void CreateAOE(AOEGraph **g) {
    // 申请内存
    *g = malloc(sizeof(AOEGraph));
    // 设置顶点与弧数
    (*g)->vexNum = 9;
    (*g)->arcNum = 11;
    // 初始化顶点值
    for (int i = 0; i < (*g)->vexNum; ++i) {
        (*g)->vertices[i].data = i + 1;
        (*g)->vertices[i].firstArc = NULL;
    }
    // 构建 AOE 网
    for (int i = 0; i < (*g)->arcNum; ++i) {
        // 开始结点
        int init = arr[3 * i];
        // 结束结点
        int end = arr[3 * i + 1];
        // 路径长度
        int dut = arr[3 * i + 2];
        AOEArcNode *p = malloc(sizeof(AOEArcNode));
        p->idx = LocateAoeVex(*(*g), end);
        p->nextArc = NULL;
        p->dut = dut;
        // 赋值指向结点
        int locate = LocateAoeVex(*(*g), init);
        p->nextArc = (*g)->vertices[locate].firstArc;
        (*g)->vertices[locate].firstArc = p;
    }
}

int LocateAoeVex(AOEGraph g, int v) {
    for (int i = 0; i < g.arcNum; i++) {
        if (g.vertices[i].data == v) {
            return i;
        }
    }
    return -1;
}

Stack t;

bool AOETopoLogicalOrder(AOEGraph *g) {
    // 创建记录各顶点入度的数组
    int inDegree[g->vexNum];
    // 统计各顶点的入度
    FindInDegree(g, inDegree);
    // 建立栈结构
    Stack s;
    Init_Stack(&s);
    Init_Stack(&t);
    // 初始化最早开始时间数组
    for (int i = 0; i < g->vexNum; ++i) ve[i] = 0;
    // 查找度为 0 的顶点，作为起始点
    for (int i = 0; i < g->vexNum; ++i) {
        if (!inDegree[i]) {
            Stack_Push(&s, i);
        }
    }
    int count = 0;
    // 栈为空作为结束标识
    while (!Stack_Empty(&s)) {
        // 弹栈，并记录栈中保存的顶点所在邻接表数组中的位置
        int index;
        Stack_Pop(&s, &index);
        // 压栈, 为求各边的最晚开始时间做准备
        Stack_Push(&t, index);
        count++;
        // 依次查找跟该顶点相链接的顶点，如果初始入度为1，当删除前一个顶点后，该顶点入度为0
        for (AOEArcNode *p = g->vertices[index].firstArc; p; p = p->nextArc) {
            // 当前索引
            VertexType k = p->idx;
            // 将入度为 0 的压入栈
            if (!(--inDegree[k])) {
                // 顶点为 0, 入栈
                Stack_Push(&s, k);
            }
            // 如果边的源点的最长路径长度加上边的权值比汇点的最长路径长度还长，就覆盖ve数组中对应位置的值，
            // 最终结束时，ve数组中存储的就是各顶点的最长路径长度。

            printf("index: %d, ve[index]: %d , p-dut: %d, k: %d, ve[k]: %d\n", index, ve[index], p->dut, k, ve[k]);
            if (ve[index] + p->dut > ve[k]) {
                ve[k] = ve[index] + p->dut;
            }
            printf("index: %d, ve[index]: %d , p-dut: %d, k: %d, ve[k]: %d\n", index, ve[index], p->dut, k, ve[k]);
            printf("======================================================\n");
        }
    }
    //如果count值小于顶点数量，表明有向图有环
    if (count < g->vexNum) {
        printf("该图有回路");
        return false;
    }

    return true;
}

void FindInDegree(AOEGraph *g, int inDegree[]) {
    // 初始化数组，默认初始值全部为0
    for (int i = 0; i < g->vexNum; i++) {
        inDegree[i] = 0;
    }
    // 遍历邻接表, 根据各链表中结点的数据域存储的各顶点位置下标，在arr数组相应位置+1
    for (int i = 0; i < g->vexNum; ++i) {
        // 查询第一条弧
        AOEArcNode *p = g->vertices[i].firstArc;
        // 遍历
        while (p) {
            inDegree[p->idx]++;
            p = p->nextArc;
        }
    }
}

void CriticalPath(AOEGraph *g) {
    // 初始化最晚开始时间, 最晚开始时间的初始值都是18, 即关键路径长度
    for (int i = 0; i < g->vexNum; i++) {
        vl[i] = ve[g->vexNum - 1];
    }
    printf("最晚开始时间栈t: ");
    Stack_Print(&t);
    // 循环计算
    while (!Stack_Empty(&t)) {
        int j, k;
        // 出栈
        Stack_Pop(&t, &j);
        // 遍历计算最晚发生时间
        for (AOEArcNode *p = g->vertices[j].firstArc; p; p = p->nextArc) {
            // 相邻数组的下标
            k = p->idx;
            // 计算最晚发生时间
            if (vl[k] - p->dut < vl[j]) {
                vl[j] = vl[k] - p->dut;
            }
        }
    }
    // 打印最早开始时间, 最晚开始时间, 是否是关键路径
    for (int l = 0; l < g->vexNum; ++l) {
        for (AOEArcNode *p = g->vertices[l].firstArc; p; p = p->nextArc) {
            // 位置索引
            int m = p->idx;
            //求各边的最早开始时间e[i],等于ve数组中相应源点存储的值
            int ee = ve[l];
            //求各边的最晚开始时间l[i]，等于汇点在vl数组中存储的值减改边的权值
            int el = vl[m] - p->dut;
            //判断e[i]和l[i]是否相等，如果相等，该边就是关键活动，相应的用*标记；反之，边后边没标记
            char tag = (ee == el) ? '*' : ' ';
            printf("当前位置: V%d, 目标位置: V%d, 权值: %3d, 最早开始时间: %3d, 最晚开始时间: %3d, 关键路径: %2c\n", l+1, m + 1, p->dut, ee, el, tag);
        }
    }

}











